package com.meterhuang;

import lombok.extern.slf4j.Slf4j;

/**
 * [middle]
 * 给你两个【非空】的链表，表示两个非负的整数。它们每位数字都是按照【逆序】的方式存储的，并且每个节点只能存储【一位】数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 *
 * 来源链接：https://leetcode-cn.com/problems/add-two-numbers
 *
 * 示例：
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 * 2->4->3
 * 5->6->4
 * result: 7->0->8
 *
 *
 * @author meterhuang
 * @date 2021/04/08 9:56
 */
@Slf4j
public class AddTwoNumber {

	public static void main(String[] args) {
		ListNode l1 = new ListNode(9);
		ListNode l2 = new ListNode(9);
		l1.next = new ListNode(9);
		l2.next = new ListNode(9);
		l1.next.next = new ListNode(9);
		l2.next.next = new ListNode(9);
		l1.next.next.next = new ListNode(9);
		l2.next.next.next = new ListNode(9);
		l1.next.next.next.next = new ListNode(9);
		l1.next.next.next.next.next = new ListNode(9);
		ListNode listNode = addTwoNumbersV2(l1, l2);
		log.info("{}", listNode);
	}

	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode node = new ListNode(0);
		traverse(l1, l2, node);
		return node;
	}

	public static ListNode addTwoNumbersV2(ListNode l1, ListNode l2) {
		ListNode head = null, tail = null;
		int carry = 0;
		while (l1 != null || l2 != null) {
			int a = (l1 == null ? 0 : l1.val);
			int b = (l2 == null ? 0 : l2.val);
			int sum = a + b + carry;
			carry = sum / 10;
			if (head == null) {
				head = tail = new ListNode(sum % 10);
			} else {
				tail.next = new ListNode(sum % 10);
				tail = tail.next;
			}
			if (l1 != null) {
				l1 = l1.next;
			}
			if (l2 != null) {
				l2 = l2.next;
			}
		}
		if (carry > 0) {
			tail.next = new ListNode(carry);
		}
		return head;
	}

	public static void traverse(ListNode l1, ListNode l2, ListNode node) {
		if (l1 == null && l2 != null) {
			node.val += l2.val;
			if (node.val < 10 && l2.next == null) {
				return;
			} else {
				condition(l2, node);
				traverse(null, l2.next, node.next);
			}
		}
		if (l1 != null && l2 == null) {
			node.val += l1.val;
			if (node.val < 10 && l1.next == null) {
				return;
			} else {
				condition(l1, node);
				traverse(l1.next, null, node.next);
			}
		}
		if (l1 == null && l2 == null) {
			return;
		}
		if (l1 != null && l2 != null) {
			node.val += l1.val + l2.val;
			if (node.val >= 10) {
				node.next = new ListNode(1);
				node.val = node.val % 10;
				traverse(l1.next, l2.next, node.next);
			} else {
				if (l1.next == null && l2.next == null) {
					return;
				}
				node.next = new ListNode(0);
				traverse(l1.next, l2.next, node.next);
			}
		}
	}

	private static void condition(ListNode l, ListNode node) {
		if (node.val >= 10) {
			node.next = new ListNode(1);
		} else {
			if (l.next != null) {
				node.next = new ListNode(0);
			}
		}
		int mod = node.val % 10;
		node.val = mod;
		if (l.next == null) {
			return;
		}
	}

	static class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}
}
